Halftoning describes the process of displaying an image on a device which is capable of representing only a finite, discrete number of tone levels. The position and arrangement of the discrete picture elements should create the illusion of a continuous-tone image. Using the traditional halftoning techniques of clustered-dot ordered dither and dispersed-dot ordered dither, undesirable visual patterns often appear, caused by the fact that the dots are placed along a distinct, rectangular (or sometimes hexagonal) grid. For colored images, there is the additional disadvantage of moire patterns, resulting from the interaction of the spatial frequencies of the halftone patterns of the individual primary colors.
To overcome some of these difficulties, halftoning methods which incorporate randomness have been developed to eliminate the distinctly periodic patterns of ordered dither. In addition, colored images rendered with random dither are free of moire patterns. The earliest attempts to incorporate randomness used white noise, in which all spatial frequencies were represented equally. Although images rendered with white noise dither are free of periodic artifacts, the images nevertheless looked too grainy, which is caused by the presence of low spatial frequencies in the halftone pattern. If the low frequency or "pink noise" content of the signal is eliminated, the remaining "blue noise" retains only higher spatial frequencies. In a book titled Digital Halftoning, by R. A. Ulichney, it was disclosed that images rendered with blue noise dither possess sharp detail and are free of the visual artifacts of ordered dither.
Blue noise, or more generally, dispersed-dot stochastic halftoning offers superior visual quality. The earliest blue noise method, error diffusion, considers the quantization error in neighboring pixels when deciding how to quantize the current pixel. Other techniques incorporate models of the printing device's physical behavior, or human visual perception, or a combination of both considerations. Examples of these other techniques include the minimum visual modulation approach described in an article titled Design of Minimum Visual Modulation Halftone Patterns, by J. Sullivan, L. Ray, and R. Miller; modified error diffusion, disclosed in an article titled Model-Based Halftoning, by T. N. Pappas and D. L. Neuhoff; least-squares model-based halftoning, disclosed in an article titled Least-Square Model-Based Halftoning, by T. N. Pappas and D. L. Neuhoff; and direct binary search, disclosed in an article titled Model-based Halftoning Using Direct Binary Search, by M. Analoui and J. P. Allebach.
The minimum visual modulation approach described by Sullivan et al. builds a set of 256 binary images (one for each gray level) by optimizing each binary image according to a human visual modulation transfer finction. The minimization technique of simulated annealing leads toward an optimal solution, however, the computational costs of each comparison is expensive, requiring a Fourier transform of each potential dot profile. The advantage is that, once this set has been generated, an image may be rendered quickly by simply matching each gray level to the appropriate binary image. The other conventional techniques offer better quality, but all rely upon image-dependent feedback, and require substantially more computation when rendering the image.
Halftoning using a dither array sacrifices some of the qualities of the image-dependent model-based approaches, but offers considerably greater speed when rendering the image. A dither array is a two-dimensional arrangement of numbers used to produce a halftone pattern. In typical applications, the numbers will be integers in the range from zero (0) through two hundred and fifty-five (255), inclusive. To produce a halftone pattern for a gray level "g" in the range of 0.ltoreq.g.ltoreq.255, every location in the dither array &lt;g will be marked with a dot. Each resulting "dot profile" (i.e., a binary image representing a constant gray level) must necessarily be a subset of all darker dot profiles. Typically, a dither array is created one dot profile at a time.
It is usually impractical to create a dither array as large as the image which is to be rendered. Therefore, the dither array typically is "tiled," or repeated periodically, as many times as needed to cover the image. Accordingly, the dither array must be free of any visual artifacts which would result in periodic patterns. The primary advantage of a dither array is its speed, which is due to the fact that for each pixel in the image, it is necessary to check only a single threshold value in the dither array.
An early dispersed-dot stochastic dither array was an adaptation of Sullivan's minimum visual modulation approach. By imposing the additional constraint that the bit patterns be "correlated" with one another, a dither array could be generated instead of using a set of 256 uncorrelated bit patterns (i.e., dot profiles). This conventional correlation approach was described in U.S. Pat. No. 5,214,517, by Sullivan et al.
A later patent, U.S. Pat. No. 5,111,310, by Parker et al. discloses the use of a blue noise mask. The Parker blue noise mask builds successive levels of the dither array by filtering the Fourier transform of each dot profile with a blue noise frequency distribution. The filtered dot profile is compared against the original dot profile to determine where dots should be added or removed, in order to create the next level (either higher or lower in gray scale level). Ulichney's void-and-cluster algorithm, disclosed in an article titled The Void-And-Cluster Method for Dither Array Generation, by R. A. Ulichney provides a fast, simple algorithm for generating a blue noise dither array, based upon the spatial distances between the pixels in each dot profile. Although this method is quick, its quality falls short of the optimal solution. Improvements have been made to both the blue noise mask and the void-and-cluster algorithm, discussed in an article titled Modified Approach to the Construction of the Blue Noise Mask, by M. Yao and K. J. Parker, and a patent titled Halftone Images Using Special Filters, U.S. Pat. No. 5,317,418, by Qian Lin. Both of these conventional approaches are presently susceptible to local minima, as they are based upon greedy optimization techniques.
Stochastic screening combines the high quality of error diffusion with the high speed of screening by use of a threshold array. For color printing, stochastic screens may be used for each color plane. In some situations, each color plane must be rendered individually, without any knowledge of the other color planes. In one example, a "dot-on-dot" method uses the same threshold array for each color plane. Another example is a "shifting" method which shifts the threshold array by a different offset distance for each color plane. Another method called "fixed partitioning" divides (i.e., partitions) the threshold range into "N" equally sized subranges, which are then used as the lightest set of subranges for each of the N planes.
When multiple color planes are combined together (i.e., superimposed or superpositioned), the individual stochastic screens should interact with each other so that the combination of dots from more than one plane should still produce a blue noise distribution. While any method of stochastic screening may be extended to color printing, the various methods used in the past each have their advantages and disadvantages. For example, the dot-on-dot method is sensitive to registration error and it fails to spread out the dots from multiple planes, which gives unnecessarily low spatial frequencies among the lighter tones. However, if dot placement is sufficiently consistent, and registration between color planes is sufficiently good, the dot-on-dot approach can also give reliable color consistency.
Another simple approach is to shift the threshold array by some horizontal and vertical offset for each of the color planes. Typically, the offsets for different planes will be mutually prime numbers (i.e., sharing no common divisors) to avoid the potential for periodic artifacts. The shifting method spreads out the dots for multiple color planes, but the resultant combination of dots contains too much white noise.
If there are only two color planes, the threshold array may be negated or inverted for the second color plane. For each threshold "t" in the original threshold array, the threshold at the same location in the second array will be the quantity "255-t" (assuming that the threshold array values are in the range of 0-255). Thus, the lightest thresholds in one array will become the darkest thresholds in the negated array and vice versa. One color will use the original array and the other color will use the negated array, and the two colors will overlap one another only when there is more than 100% total coverage. In a paper titled, "Color Halftoning With Blue Noise Masks," by M. Yao and K. G. Parker, the negating method is generalized for three or more color planes. For lighter shades, the negating method appears just as noisy as the shifting method. In general, the lightest thresholds tend to be located near the darkest thresholds in a given threshold array. In the negated array, the darkest thresholds will become the lightest thresholds. Thus, the lightest thresholds of the original array will tend to be located near the lightest thresholds in the negated array, and the pattern formed by the superposition of the two threshold arrays will appear noisy, at least in the lighter shades.
This problem will be most prominent when the lighter tones of individual color planes are combined together. For darker shades, the quality will steadily improve for two reasons: (1) the greater the separation between a threshold and its negated value, the less likely the two thresholds, together, form a pleasing pattern, although this aspect becomes least prominent for thresholds that are in the center of the intensity range; and (2) as more dots are added to the pattern, the spatial frequency increases, and the noise becomes more difficult to discern, although this aspect becomes least prominent when there is complete saturation.
As related above, both the shifting method and the negating method perform poorly for light shades, however, as the shades become darker, the negating method improves in quality compared to the shifting method. See U.S. Pat. No. 5,341,228, by Parker and Mitsa for further information.
The above-referenced Yao and Parker article suggests that dividing the range of threshold values among each of the color planes could be utilized in a fixed partitioning scheme. While the fixed partitioning method does a better job than the shifting method for color combinations that are near 100% total coverage, for lighter shades the fixed partitioning method appears just as noisy as the shifting method.
All of the methods described above for stochastic screening in color allow for each color plane to be rendered independently of the other color planes. In some cases, this restriction facilitates the overall design. However, the lighter shades are generally too noisy when combining the color planes. It would be advantageous to provide a new method of color halftoning with stochastic screens in which each of the individual stochastic screens is designed so that all of the screens may fit together to produce a combined pattern of dots that has a blue noise distribution, thereby presenting a pleasing result when combining all of the color planes.